package main.sort;

public class QuickSort extends BaseSort {
    public QuickSort(int[] array) {
        super(array);
        this.name = "快速排序";
    }

    /**
     * 选中一个元素作为判定基准，每一轮将这个元素放在其应当在的下标
     * 从而将数组分割为左右两部分，再次重复左右两边直到左右仅剩一个元素
     * <br>
     * [1, 7, 6, 5, 4, 3, 2, 8]<br>
     * [1, 7, 6, 5, 4, 3, 2, 8]<br>
     * [1, 2, 6, 5, 4, 3, 7, 8]<br>
     * [1, 2, 6, 5, 4, 3, 7, 8]<br>
     * [1, 2, 3, 5, 4, 6, 7, 8]<br>
     * [1, 2, 3, 5, 4, 6, 7, 8]<br>
     * [1, 2, 3, 4, 5, 6, 7, 8]
     */
    @Override
    public void sort() {
        sort(array, 0, array.length - 1);
    }

    public void sort(int[] array, int left, int right) {
        int i = left, j = right;
        if (i < j) {
            int index = array[left];
            while (i < j) {
                while (i < j && array[j] >= index) {
                    j--;
                }
                if (i < j) {
                    array[i++] = array[j];
                }
                while (i < j && index >= array[i]) {
                    i++;
                }
                if (i < j) {
                    array[j--] = array[i];
                }
            }
            array[i] = index;

            print();
            sort(array, left, i - 1);
            sort(array, i + 1, right);
        }
    }
}
